package netflow;

import java.util.*;

/**
 * Class to calculate the maximum flow in a given network using Ford Fulkerson
 * Algorithm
 * 
 * @author Rashmi
 * 
 */
public class FordFulkerson
{
  private HashMap<Edge, Double> edgeFlow = new HashMap<Edge, Double>();
  private HashMap<Edge, Double> initialCapacityMap = new HashMap<Edge, Double>();
  ArrayList<Edge> forwardEdges = new ArrayList<Edge>();
  private double maxvalue = 0.0; // current value of max flow
  private Vertex s;
  private Vertex t;
  private SimpleGraph SG;

  public FordFulkerson(SimpleGraph SG, Vertex s, Vertex t)
  {
    this.s = s;
    this.t = t;
    this.SG = SG;
    calculateMaxFlow();
  }

  private void calculateMaxFlow()
  {
    maxvalue = 0.0;

    // Initialize residualCapacity in edges to max capacity
    // Create new edges for reverse direction with capacity 0
    Iterator eI, eI2;
    for (eI = SG.edges(); eI.hasNext();)
    {
      Edge e1 = (Edge) eI.next();
      forwardEdges.add(e1);
      initialCapacityMap.put(e1, (Double) e1.getData());
      edgeFlow.put(e1, new Double(0.0));
    }
    for (Edge e : forwardEdges)
    {
      if (findEdgeInForwardEdgesList(e.getSecondEndpoint(), e.getFirstEndpoint()) == false)
      {
        // Backward edge not present. Create a dummy edge with capacity 0.
        Edge newEdge = SG.insertEdge(e.getSecondEndpoint(), e.getFirstEndpoint(), new Double(0.0),
            "backwardEdge");
        edgeFlow.put(newEdge, new Double(0.0));
      }
    }

    path.clear();
    edgeVisited.clear();
    vertexFinished.clear();
    while (hasPath(s, t))
    {
      maxvalue += augmentFlow(SG, path);

      path.clear();
      edgeVisited.clear();
      vertexFinished.clear();

    }

    System.out.println("MaxFlow: " + maxvalue);

  }

  private double augmentFlow(SimpleGraph SG, ArrayList<Edge> path)
  {
    // Calculate minimum flow possible
    double minCapacity = Double.POSITIVE_INFINITY;
    for (Edge e1 : path)
    {
      minCapacity = ((Double) e1.getData()).doubleValue() < minCapacity ? ((Double) e1.getData())
          .doubleValue() : minCapacity;
    }

    for (Edge uvEdge : path)
    {
      // decrease capacity in this edge;
      double residualCapacity = ((Double) uvEdge.getData()).doubleValue() - minCapacity;
      uvEdge.setData(new Double(residualCapacity));
      Edge vuEdge = findEdge(uvEdge.getSecondEndpoint(), uvEdge.getFirstEndpoint());

      // Increase capacity on the backward edge
      residualCapacity = ((Double) vuEdge.getData()).doubleValue() + minCapacity;
      vuEdge.setData(new Double(residualCapacity));
    }
    return minCapacity;
  }

  private Edge findEdge(Vertex v1, Vertex v2)
  {
    Iterator eI;
    for (eI = SG.edges(); eI.hasNext();)
    {
      Edge e1 = (Edge) eI.next();
      if (e1.getFirstEndpoint().equals(v1) && e1.getSecondEndpoint().equals(v2))
      {
        return e1;
      }
    }
    return null;
  }

  private boolean findEdgeInForwardEdgesList(Vertex v1, Vertex v2)
  {
    for (Edge e2 : forwardEdges)
    {
      if (e2.getFirstEndpoint().equals(v1) && e2.getSecondEndpoint().equals(v2))
      {
        return true;
      }
    }
    return false;
  }

  HashMap<Edge, Boolean> edgeVisited = new HashMap<Edge, Boolean>();
  HashMap<Vertex, Boolean> vertexFinished = new HashMap<Vertex, Boolean>();
  ArrayList<Edge> path = new ArrayList<Edge>();

  private boolean hasPath(Vertex source, Vertex dest)
  {
    if (source.equals(dest))
      return true;
    if (vertexFinished.containsKey(source))
      return false;
    Iterator<Edge> sourceEdges = source.incidentEdgeList.iterator();
    for (; sourceEdges.hasNext();)
    {
      Edge e1 = (Edge) sourceEdges.next();
      if (e1.getFirstEndpoint().equals(source))
      {
        // Consider only edges that start from here.
        if (!edgeVisited.containsKey(e1))
        {
          // mark as visited
          edgeVisited.put(e1, Boolean.TRUE);
          if (((Double) e1.getData()).doubleValue() > 0.0)
          {
            if (hasPath(e1.getSecondEndpoint(), dest))
            {
              // Destination found in this path.. Add this edge to the path
              path.add(e1);
              return true;
            }
          }

        }
      }
    }
    vertexFinished.put(source, Boolean.TRUE);
    return false;

  }

  public static void main(String args[])
  {
    SimpleGraph SG = new SimpleGraph();
    GraphInput.LoadSimpleGraph(SG, "src/netflow/meshGenerator/smallMesh.txt");

    Vertex s1 = null, t1 = null;
    Iterator i;
    Vertex v;
    Edge e;
    System.out.println("Iterating through vertices...");
    for (i = SG.vertices(); i.hasNext();)
    {
      v = (Vertex) i.next();
      System.out.println("found vertex " + v.getName());
      if (v.getName().equals("s"))
        s1 = v;
      else if (v.getName().equals("t"))
        t1 = v;
      Iterator j;
      for (j = SG.incidentEdges(v); j.hasNext();)
      {
        e = (Edge) j.next();
        System.out.println("  found edge " + e.getData());
      }
    }

    try
    {
      long startTime = System.currentTimeMillis();
      new FordFulkerson(SG, (Vertex) s1, (Vertex) t1);
      long endTime = System.currentTimeMillis();
      long totalTime = endTime - startTime;
      System.out.println("Total Time Taken-" + totalTime + " msec");
      totalTime = (long) Math.log(totalTime);
      System.out.println("Log Time Taken-" + totalTime + " msec");
    } catch (Exception e1)
    {
      e1.printStackTrace();
    }

  }
}